package com.zsj.Tree;

/**
 * 二叉搜索树在添加和删除的时候可能会失衡 <br/>
 * 而通过在删除和添加时进行旋转的操作来保证二叉树的平衡性
 *
 * @author zsj
 * @version 1.0
 * @date 2024/4/15 13:31
 * @description 自平衡二叉搜索树
 */
public class AVLTree {
    static class AVLNode {
        int key;
        Object value;
        AVLNode left;
        AVLNode right;
        int height = 1;


        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

    }

    //获取节点高度
    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    /**
     * 根据传入节点更新它的高度
     *
     * @param node 传入节点
     */
    private void updateHeight(AVLNode node) {
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }

    /**
     * 平衡因子 balance factor = 左子树高度-右子树高度
     *
     * @param node 传入节点
     * @return 0, 1,-1为平衡 :>1(左高)  <-1(右边高) 不平衡
     */
    private int balanceFactor(AVLNode node) {
        return height(node.left) - height(node.right);
    }



}
